package algo.dijkstra;

import algo.Edge;
import algo.Graph;
import algo.Node;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 *
 * @author robin
 */
public class DijkstrasAlgorithm {

    private final Graph graph;
    private Node startNode;
    //a node is moved to the settled set if a shortest path from the source to this 
    //node has been found
    private Set<Node> settledNodes;
    //initial state of the nodes
    private Set<Node> unsettledNodes;
    private Map<Node, Node> predecessors;
    private Map<Node, Integer> distance;
    private volatile boolean dijkstraMappingProgress;
    private Node destNode;
    private long algorithmTime, startTime, stopTime;

    public DijkstrasAlgorithm(Graph graph, Node startNode) {
        this.graph = graph;
        this.startNode = startNode;
        algorithmTime = 0;
    }

    public void execute(Node destination) {
        startTime = System.currentTimeMillis();
        destNode = destination;
        dijkstraMappingProgress = true;
        settledNodes = new HashSet<Node>();
        unsettledNodes = new HashSet<Node>();
        distance = new HashMap<Node, Integer>();
        predecessors = new HashMap<Node, Node>();
        distance.put(startNode, 0);
        unsettledNodes.add(startNode);

        while (unsettledNodes.size() > 0 && dijkstraMappingProgress) {
            Node node = getMinimum(unsettledNodes);

            settledNodes.add(node);
            unsettledNodes.remove(node);
            findMinimalDistances(node);
        }
    }

    private void findMinimalDistances(Node node) {
        List<Node> aanliggendeNodes = getNeighbors(node);

        for (Node target : aanliggendeNodes) {
            int totalDistance = getShortestDistance(node) + getDistance(node, target);

            if (getShortestDistance(target) > totalDistance) {
                distance.put(target, totalDistance);

                if (target.equals(destNode)) {
                    dijkstraMappingProgress = false;
                    System.out.println("breaking algorithm");
                }
                predecessors.put(target, node);
                unsettledNodes.add(target);
            }
        }
    }

    private Node getMinimum(Set<Node> nodes) {
        Node min = null;

        for (Node node : nodes) {
            if (min == null) {
                min = node;
            } else {
                if (getShortestDistance(node) < getShortestDistance(min)) {
                    min = node;
                }
            }
        }
        return min;
    }

    private List<Node> getNeighbors(Node node) {
        List<Node> neighbors = new ArrayList<Node>();

        for (Edge edge : graph.getEdges()) {
            if (edge.src.equals(node) && !isSettled(edge.dst)) {
                neighbors.add(edge.dst);
            }
        }
        return neighbors;
    }

    private int getShortestDistance(Node destination) {
        Integer d = distance.get(destination);

        if (d == null) {
            return Integer.MAX_VALUE;
        } else {
            return d;
        }
    }

    private int getDistance(Node node, Node target) {
        for (Edge edge : graph.getEdges()) {
            if ((edge.src.equals(node))
                    && (edge.dst.equals(target))) {
                return edge.cost;
            }
        }
        throw new RuntimeException("shouldn't happen");
    }

    /**
     * returns the path from the source to the selected target if no path
     * exists, it will return null
     *
     * @param node
     * @return
     */
    private boolean isSettled(Node node) {
        return settledNodes.contains(node);
    }

    public long getAlgorithmTime() {
        return algorithmTime;
    }

    public LinkedList<Node> getPath(Node target) {
        LinkedList<Node> path = new LinkedList<Node>();
        Node step = target;
        //controleren of er een path betaat

        if (predecessors.get(step) == null) {
            return null;
        } else {
            path.add(step);

            while (startNode.block != step.block) {
                System.out.println(step.block);
                step = predecessors.get(step);
                path.add(step);
            }
            stopTime = System.currentTimeMillis();
            algorithmTime = stopTime - startTime;
            //correct sorteren
            Collections.reverse(path);

            return path;
        }
    }
}